Low Density Parity Code (LDPC) decoders are current generation iterative soft-input forward error correction (FEC) decoders that have found increasing popularity in FEC applications where low error floor and high performance are desired. LDPC decoders are defined in terms of a two-dimensional matrix, referred to as an H matrix, which describes the connections between the data bits and the parity bits of an LDPC code. Thus, the H matrix comprises rows and columns of data and parity information. Decoding an LDPC codeword involves associating the LDPC codeword with the H matrix and solving, based on a two-step iterative method, the equations generated from the association of the LDPC codeword and the H matrix. Soft-decoding the codeword causes convergence of the solved codeword with the true codeword; convergence is achieved over a number of iterations and results in a corrected codeword with no errors.
A category of LDPC codes, known as quasi-cyclic (QC) codes, generates an H matrix with features that improve the ease of implementing the LDPC encoder and decoder. In particular, it is possible to generate a QC-LDPC H matrix where some rows are orthogonal to each other. These orthogonal rows are treated as a layer, and rows within a layer can be processed in parallel, thus reducing the iterative cost of the decoder. Furthermore, a layered LDPC decoder can process a layer by combining the two-step iterations into a single one-step operation. It is advantageous to reduce the number of iterations necessary to decode an LDPC codeword.
Performance of a given FEC decoder may be measured, according to one exemplary metric, by comparing the frame error rate (FER) at the decoder output to the bit error rate (BER) at the decoder input. An input bit error can be, for example, a random bit flip caused by noise between a transmitter and a receiver. An output frame error represents an uncorrectable codeword, which results in a decode failure. Generally, more input bit errors will cause more output frame errors. However, some FEC decoders or decoder configurations can handle a given BER better than other decoders or decoder configurations. Graphing the FER vs. BER relationship in a “waterfall”-like graph can show relative performance of different FEC decoders or decoder configurations.
FIG. 1 is a graph showing an example of FER performance of a conventional layered LDPC decoder. The graph shows the LDPC decoder according to four different configurations: having 5 maximum iterations, 10 maximum iterations, 15 maximum iterations, and 20 maximum iterations. The number of maximum iterations refers to the maximum number of times the decoder will spend on processing the layers of the H matrix before the decoder abandons the decoding. It is not practical to design a decoder without a maximum number iterations limit because the decoder can become stuck decoding an uncorrectable codeword.
When the decoder abandons or terminates decoding before convergence, the decoder effectively declares that the received codeword is uncorrectable. Since the decoder does not achieve convergence, a system relying on the FEC decoder will have to resort to other means to recover the information originally transmitted in the codeword. For example, the system may use communication protocols to cause re-transmission of the codeword. For this reason, it is undesirable for the decoder to fail to achieve convergence of a codeword.
FIG. 1 shows that increasing the maximum number of iterations of the LDPC decoder improves the FER performance, leading to fewer instances where the decoder terminates decoding before codeword convergence. Therefore, by this one measure, it is desirable to increase the maximum number of iterations of the LDPC decoder.
However, it may not always be desirable to increase the maximum number of iterations of the LDPC decoder because frequently running the decoder up to the maximum number of iterations decreases the raw processing throughput of the decoder.
FIG. 2 is a graph showing an average number of iterations for the LDPC decoder to decode a codeword vs. the input BER of the codeword. The LDPC decoder is configured to 20 maximum iterations. When the BER at the LDPC decoder input increases, the LDPC decoder takes, on average, more time to decode each codeword. This expected trend has a linear slope from approximately 0.2*10^-3 to 3*10^-3 BER. At approximately 3*10^-3 BER, the slope increases significantly; therefore, from approximately 3*10^-3 to 4*10^-3 BER, the performance of the LDPC decoder diminishes more for each increasing BER than in the 0.2*10^-3 to 3*10^-3 BER range.
This change in slope, or “knee”, at region 10 in the graph of FIG. 2 indicates the input BER at which many codeword decodes run to the maximum number of iterations. When the average iteration load becomes dominated by decode runs to the maximum number of iterations (e.g. 20 iterations), average iteration value quickly increases, as shown in FIG. 2. Generally, a higher average iteration value corresponds to longer decode times and lower raw throughput at the decoder.
More specifically, however, for every average iteration data point in FIG. 2, a cumulative distribution function (CDF) can be graphed to show the probabilities of various iteration values included in the average iteration data point. FIG. 3 is a graph showing the CDF of the 3 average iterations data point for the LDPC decoder configured to 20 maximum iterations.
FIG. 3 shows that the LDPC decoder will take longer than 6 iterations to process a codeword approximately once every 1,000,000 codewords; furthermore, the LDPC decoder will take longer than 9 iterations approximately once every 100,000,000 codewords. Finally, the LDPC decoder will run to the maximum iteration limit (i.e. 20 iterations) approximately once every 10,000,000,000 codewords.
It is clear in FIG. 3 that reducing the maximum number of iterations will change the CDFs of all average iteration data points in FIG. 2. Moreover, reducing the maximum number of iterations will shift the location of the “knee” in FIG. 2, leading to generally lower average iteration counts and lower power consumption. However, as shown in FIG. 1, it is also clear that reducing the maximum number of iterations has a detrimental impact on FER performance, leading to more decode failures.
It is, therefore, desirable to provide an FEC decoder with high FER performance, high raw throughput and low power consumption.